package com.dataStructures.sort;

import java.util.Arrays;

/**
 * 基数排序（桶排序）
 */
public class RadixSort {
	public static void main(String[] args) {
		int[] arr = {53, 3, 542, 748, 14, 214};
		System.out.println("排序前：" + Arrays.toString(arr));
		radixSort(arr);
		System.out.println("排序后：" + Arrays.toString(arr));

		// 批量测试
		int[] arrBatch = new int[80000];
		for (int i = 0; i < 80000; i++) {
			arrBatch[i] = (int) (Math.random() * 8000000);
		}
		long begin = System.currentTimeMillis();
		radixSort(arrBatch);
		System.out.println("coast time:" + (System.currentTimeMillis() - begin));
	}

	/**
	 * 桶排序
	 */
	public static void radixSort(int[] arr) {
		// 得到数组中最大的数
		int max = arr[0];
		for (int n : arr) {
			if (n > max) {
				max = n;
			}
		}
		// 得到最大数的位数
		int maxlength = (max + "").length();

		// 定义一个二维数组，表示 10 个桶, 每个桶里放的数就是一个一维数组
		// 为了防止在放入数的时候，数据溢出，则每个一维数组(桶)，大小定为 arr.length（空间换时间）
		int[][] bucket = new int[10][arr.length];

		// 为了记录每个桶中，实际存放了多少个数据,我们定义一个一维数组来记录各个桶的每次放入的数据个数
		// 比如:bucketEleCounts[0] , 记录的就是 bucket[0] 桶的放入数据个数
		int[] bucketEleCounts = new int[10];


		for (int i = 0, n = 1; i < maxlength; i++, n *= 10) {
			for (int j = 0; j < arr.length; j++) {
				// 取出每个元素的对应位的值, 放入到对应的桶中
				int digitOfElement = arr[j] / n % 10;
				bucket[digitOfElement][bucketEleCounts[digitOfElement]] = arr[j];
				bucketEleCounts[digitOfElement]++;
			}

			// 按照这个桶的顺序(一维数组的下标依次取出数据，放入原来数组)
			int index = 0;
			// 遍历每一桶，并将桶中是数据，放入到原数组
			for (int j = 0; j < bucketEleCounts.length; j++) {
				if (bucketEleCounts[j] != 0) {
					for (int k = 0; k < bucketEleCounts[j]; k++) {
						arr[index++] = bucket[j][k];
					}
				}

				//第 i+1 轮处理后，需要将每个 bucketElementCounts[k] = 0 !!!!
				bucketEleCounts[j] = 0;
			}
		}
	}
}